<!DOCTYPE html>



  


<html class="theme-next pisces use-motion" lang="zh-Hans">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">






  
  
  <link rel="stylesheet" media="all" href="/lib/Han/dist/han.min.css?v=3.3">




<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.3" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.3">


  <link rel="icon" type="image/png" sizes="32x32" href="/img/icon.png?v=5.1.3">


  <link rel="icon" type="image/png" sizes="16x16" href="/img/icon.png?v=5.1.3">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.3" color="#222">





  <meta name="keywords" content="cayun's blog, IT, ACM/ICPC, blog, cayun" />










<meta property="og:type" content="website">
<meta property="og:title" content="cayun&#39;s blog">
<meta property="og:url" content="http://localhost/page/8/index.html">
<meta property="og:site_name" content="cayun&#39;s blog">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="cayun&#39;s blog">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Pisces',
    version: '5.1.3',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://localhost/page/8/"/>





  <title>cayun's blog</title>
  




<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
            (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
          m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
  ga('create', 'UA-93052608-1', 'auto');
  ga('send', 'pageview');
</script>


  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?1ca7c9c8011b37b0c209724dc77c24db";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left 
  page-home">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">cayun's blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <h1 class="site-subtitle" itemprop="description">不积跬步, 无以至千里!</h1>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/android_3/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/android_3/" itemprop="url">Android 弹窗 (API23)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-06-12T00:00:00+08:00">
                2017-06-12
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/Android/" itemprop="url" rel="index">
                    <span itemprop="name">Android</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/android_3/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/android_3/" class="cy_cmt_count" data-xid="android_3/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          <p>如下直接封装为一个函数，其中参数context为上下文环境，message为弹窗提示内容</p>
          <!--noindex-->
          <div class="post-button text-center">
            <a class="btn" href="/android_3/" rel="contents">
              阅读全文 &raquo;
            </a>
          </div>
          <!--/noindex-->
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/web_1/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/web_1/" itemprop="url">css使得width属性包含border, padding的方法</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-06-10T00:00:00+08:00">
                2017-06-10
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/web_1/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/web_1/" class="cy_cmt_count" data-xid="web_1/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <p>content-&gt;padding-&gt;border-&gt;margin<br>照情理来说，padding和border应该计算入width中来，但实际上，在W3C标准的浏览器中padding以及border都不计算入width部分，但是W3C提供了属性box-sizing来使得padding和border计算入width中，代码如下：</p>
<figure class="highlight css"><table><tr><td class="code"><pre><div class="line"><span class="selector-class">.class-name</span> &#123;</div><div class="line">    <span class="attribute">-moz-box-sizing</span>: border-box;</div><div class="line">    <span class="attribute">-webkit-box-sizing</span>: border-box;</div><div class="line">    <span class="attribute">box-sizing</span>: border-box;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/linux_2/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/linux_2/" itemprop="url">nginx设置域名跳转</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-06-09T00:00:00+08:00">
                2017-06-09
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/linux_2/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/linux_2/" class="cy_cmt_count" data-xid="linux_2/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <p>比如我的博客，将cayun.me跳转到www.cayun.me</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><div class="line">server &#123;</div><div class="line">    listen 80;</div><div class="line">    server_name cayun.me;</div><div class="line">    return 301 http://www.cayun.me;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/android_1/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/android_1/" itemprop="url">Android 使用HttpURLConnection进行网络异步通信方法 (API23)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-06-09T00:00:00+08:00">
                2017-06-09
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/Android/" itemprop="url" rel="index">
                    <span itemprop="name">Android</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/android_1/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/android_1/" class="cy_cmt_count" data-xid="android_1/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          <h1 id="通过修改gradle使用httpclient"><a href="#通过修改gradle使用httpclient" class="headerlink" title="通过修改gradle使用httpclient"></a>通过修改gradle使用httpclient</h1><p>google在Android API23中禁用了httpclient，虽然可以通过添加如下代码到gradle的方式重新启用</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><div class="line">android &#123;</div><div class="line">    useLibrary &apos;org.apache.http.legacy&apos;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h1 id="使用HttpURLConnection"><a href="#使用HttpURLConnection" class="headerlink" title="使用HttpURLConnection"></a>使用HttpURLConnection</h1><p>不过，这里使用android API23支持的HttpURLConnection来进行异步传输<br><br>代码原地址<a href="http://www.jianshu.com/p/3141d4e46240" target="_blank" rel="external">http://www.jianshu.com/p/3141d4e46240</a></p>
<p>首先创建一个AsynNetUtils类</p>
          <!--noindex-->
          <div class="post-button text-center">
            <a class="btn" href="/android_1/" rel="contents">
              阅读全文 &raquo;
            </a>
          </div>
          <!--/noindex-->
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/hdu4609/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hdu4609/" itemprop="url">hdu 4609 3-idiots (FFT)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-21T00:00:00+08:00">
                2017-03-21
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/hdu4609/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/hdu4609/" class="cy_cmt_count" data-xid="hdu4609/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>感觉这题<a href="http://www.cnblogs.com/kuangbin/archive/2013/07/24/3210565.html" target="_blank" rel="external">邝斌的博客</a>讲解得特别棒。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">double</span> PI = <span class="built_in">acos</span>(<span class="number">-1.0</span>);</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">ComplexFFT</span> &#123;</span></div><div class="line">    <span class="keyword">double</span> a, b;</div><div class="line"></div><div class="line">    ComplexFFT(<span class="keyword">double</span> x = <span class="number">0.0</span>, <span class="keyword">double</span> y = <span class="number">0.0</span>) &#123;</div><div class="line">        a = x; b = y;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    ComplexFFT <span class="keyword">operator</span>+(<span class="keyword">const</span> ComplexFFT &amp;u) &#123;</div><div class="line">        <span class="keyword">return</span> ComplexFFT(a + u.a, b + u.b);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    ComplexFFT <span class="keyword">operator</span>-(<span class="keyword">const</span> ComplexFFT &amp;u) &#123;</div><div class="line">        <span class="keyword">return</span> ComplexFFT(a - u.a, b - u.b);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    ComplexFFT <span class="keyword">operator</span>*(<span class="keyword">const</span> ComplexFFT &amp;u) &#123;</div><div class="line">        <span class="keyword">return</span> ComplexFFT(a * u.a - b * u.b, a * u.b + b * u.a);</div><div class="line">    &#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">ChangeFFT</span><span class="params">(ComplexFFT cp[], <span class="keyword">int</span> len)</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> i, j, k;</div><div class="line">    <span class="keyword">for</span> (i = <span class="number">1</span>, j = len / <span class="number">2</span>; i &lt; len - <span class="number">1</span>; i++) &#123;</div><div class="line">        <span class="keyword">if</span> (i &lt; j) swap(cp[i], cp[j]);</div><div class="line">        k = len / <span class="number">2</span>;</div><div class="line">        <span class="keyword">while</span> (j &gt;= k) &#123;</div><div class="line">            j -= k;</div><div class="line">            k &gt;&gt;= <span class="number">1</span>;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">if</span> (j &lt; k) j += k;</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="comment">//"on = 1" : "DFT"</span></div><div class="line"><span class="comment">//"on = -1" : "IDFT"</span></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">FFT</span><span class="params">(ComplexFFT cp[], <span class="keyword">int</span> len, <span class="keyword">int</span> on)</span> </span>&#123;</div><div class="line">    ChangeFFT(cp, len);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">2</span>; i &lt;= len; i &lt;&lt;= <span class="number">1</span>) &#123;</div><div class="line">        ComplexFFT wn(cos(-on * 2 * PI / i), sin(-on * 2 * PI / i));</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; len; j += i) &#123;</div><div class="line">            <span class="function">ComplexFFT <span class="title">w</span><span class="params">(<span class="number">1</span>, <span class="number">0</span>)</span></span>;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> k = j; k &lt; j + i / <span class="number">2</span>; k++) &#123;</div><div class="line">                ComplexFFT u = cp[k];</div><div class="line">                ComplexFFT t = w * cp[k + i / <span class="number">2</span>];</div><div class="line">                cp[k] = u + t;</div><div class="line">                cp[k + i / <span class="number">2</span>] = u - t;</div><div class="line">                w = w * wn;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">if</span> (on == <span class="number">-1</span>) &#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len; i++) cp[i].a /= len;</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">400010</span>;</div><div class="line"><span class="keyword">int</span> a[N], b[N], e[N];</div><div class="line">ComplexFFT c[N], d[N];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> T; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;T);</div><div class="line">    <span class="keyword">while</span> (T--) &#123;</div><div class="line">        <span class="built_in">memset</span>(b, <span class="number">0</span>, <span class="keyword">sizeof</span>(b));</div><div class="line">        <span class="keyword">int</span> n; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;n);</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</div><div class="line">            <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;a[i]);</div><div class="line">            b[a[i]]++;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">int</span> bn = <span class="number">100000</span>;</div><div class="line">        <span class="keyword">while</span> (b[bn] == <span class="number">0</span>) bn--;</div><div class="line">        bn++;</div><div class="line">        <span class="comment">//printf("bn = %d\n", bn);</span></div><div class="line">        <span class="keyword">int</span> len = <span class="number">1</span>;</div><div class="line">        <span class="keyword">while</span> (len &lt; bn) len &lt;&lt;= <span class="number">1</span>;</div><div class="line">        len &lt;&lt;= <span class="number">1</span>;</div><div class="line">        <span class="comment">//printf("len = %d\n", len);</span></div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len; i++)</div><div class="line">            c[i] = i &lt; bn ? ComplexFFT(b[i], <span class="number">0</span>) : ComplexFFT(<span class="number">0</span>, <span class="number">0</span>);</div><div class="line">        FFT(c, len, <span class="number">1</span>);</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len; i++)</div><div class="line">            d[i] = c[i] * c[i];</div><div class="line">        FFT(d, len, <span class="number">-1</span>);</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len; i++)</div><div class="line">            e[i] = (<span class="keyword">int</span>)(d[i].a + <span class="number">0.5</span>);</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) </div><div class="line">            e[a[i] &lt;&lt; <span class="number">1</span>]--;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len; i++)</div><div class="line">            e[i] &gt;&gt;= <span class="number">1</span>;</div><div class="line">        <span class="comment">/*</span></div><div class="line"><span class="comment">        for (int i = 0; i &lt; len; i++)</span></div><div class="line"><span class="comment">            printf("%d ", e[i]);</span></div><div class="line"><span class="comment">        printf("\n");</span></div><div class="line"><span class="comment">        */</span></div><div class="line">        sort(a, a + n);</div><div class="line">        <span class="keyword">int</span> ai = <span class="number">0</span>;</div><div class="line">        LL sum = <span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len; i++) &#123;</div><div class="line">            <span class="keyword">while</span> (ai &lt; n &amp;&amp; a[ai] &lt; i) ai++;</div><div class="line">            sum += (LL)e[i] * (n - ai);</div><div class="line">            <span class="comment">//printf("%d %d %d\n", e[i], ai, sum);</span></div><div class="line">        &#125;</div><div class="line">        LL tot = (LL)n * (n - <span class="number">1</span>) * (n - <span class="number">2</span>) / <span class="number">6</span>;</div><div class="line">        <span class="built_in">printf</span>(<span class="string">"%.7f\n"</span>, <span class="number">1</span> - <span class="number">1.0</span> * sum / tot);</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/hdu1402/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hdu1402/" itemprop="url">hdu 1402 A * B Problem Plus (FFT 压位高精度乘法)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-19T00:00:00+08:00">
                2017-03-19
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/hdu1402/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/hdu1402/" class="cy_cmt_count" data-xid="hdu1402/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>这题由于数据规模为$50000$，所以常规的直接乘法是不行的。<br>所以可以通过以下两种方式来做：</p>
<ol>
<li>FFT，时间复杂度$O(nlogn)$</li>
<li>乘法压位，可以减少$n$的范围，时间复杂度$O(n^2)$</li>
</ol>
<h1 id="FFT的解法"><a href="#FFT的解法" class="headerlink" title="FFT的解法"></a>FFT的解法</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">double</span> PI = <span class="built_in">acos</span>(<span class="number">-1.0</span>);</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">ComplexFFT</span> &#123;</span></div><div class="line">    <span class="keyword">double</span> a, b;</div><div class="line"></div><div class="line">    ComplexFFT(<span class="keyword">double</span> x = <span class="number">0.0</span>, <span class="keyword">double</span> y = <span class="number">0.0</span>) &#123;</div><div class="line">        a = x; b = y;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    ComplexFFT <span class="keyword">operator</span>+(<span class="keyword">const</span> ComplexFFT &amp;u) &#123;</div><div class="line">        <span class="keyword">return</span> ComplexFFT(a + u.a, b + u.b);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    ComplexFFT <span class="keyword">operator</span>-(<span class="keyword">const</span> ComplexFFT &amp;u) &#123;</div><div class="line">        <span class="keyword">return</span> ComplexFFT(a - u.a, b - u.b);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    ComplexFFT <span class="keyword">operator</span>*(<span class="keyword">const</span> ComplexFFT &amp;u) &#123;</div><div class="line">        <span class="keyword">return</span> ComplexFFT(a * u.a - b * u.b, a * u.b + b * u.a);</div><div class="line">    &#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">ChangeFFT</span><span class="params">(ComplexFFT cp[], <span class="keyword">int</span> len)</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> i, j, k;</div><div class="line">    <span class="keyword">for</span> (i = <span class="number">1</span>, j = len / <span class="number">2</span>; i &lt; len - <span class="number">1</span>; i++) &#123;</div><div class="line">        <span class="keyword">if</span> (i &lt; j) swap(cp[i], cp[j]);</div><div class="line">        k = len / <span class="number">2</span>;</div><div class="line">        <span class="keyword">while</span> (j &gt;= k) &#123;</div><div class="line">            j -= k;</div><div class="line">            k &gt;&gt;= <span class="number">1</span>;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">if</span> (j &lt; k) j += k;</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="comment">//"on = 1" : "DFT"</span></div><div class="line"><span class="comment">//"on = -1" : "IDFT"</span></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">FFT</span><span class="params">(ComplexFFT cp[], <span class="keyword">int</span> len, <span class="keyword">int</span> on)</span> </span>&#123;</div><div class="line">    ChangeFFT(cp, len);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">2</span>; i &lt;= len; i &lt;&lt;= <span class="number">1</span>) &#123;</div><div class="line">        ComplexFFT wn(cos(-on * 2 * PI / i), sin(-on * 2 * PI / i));</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; len; j += i) &#123;</div><div class="line">            <span class="function">ComplexFFT <span class="title">w</span><span class="params">(<span class="number">1</span>, <span class="number">0</span>)</span></span>;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> k = j; k &lt; j + i / <span class="number">2</span>; k++) &#123;</div><div class="line">                ComplexFFT u = cp[k];</div><div class="line">                ComplexFFT t = w * cp[k + i / <span class="number">2</span>];</div><div class="line">                cp[k] = u + t;</div><div class="line">                cp[k + i / <span class="number">2</span>] = u - t;</div><div class="line">                w = w * wn;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">if</span> (on == <span class="number">-1</span>) &#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len; i++) cp[i].a /= len;</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">200010</span>;</div><div class="line">ComplexFFT x1[N], x2[N], x[N];</div><div class="line"><span class="keyword">char</span> str1[N], str2[N];</div><div class="line"><span class="keyword">int</span> sum[N];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">while</span> (<span class="built_in">scanf</span>(<span class="string">"%s%s"</span>, str1, str2) != EOF) &#123;</div><div class="line">        <span class="keyword">int</span> len1 = <span class="built_in">strlen</span>(str1), len2 = <span class="built_in">strlen</span>(str2);</div><div class="line">        <span class="keyword">int</span> len = <span class="number">1</span>;</div><div class="line">        <span class="keyword">while</span> (len &lt;= len1 || len &lt;= len2) len &lt;&lt;= <span class="number">1</span>;</div><div class="line">        len &lt;&lt;= <span class="number">1</span>;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len; i++) &#123;</div><div class="line">            x1[i] = i &lt; len1 ? ComplexFFT(str1[len1 - i - <span class="number">1</span>] - <span class="string">'0'</span>, <span class="number">0</span>) : ComplexFFT(<span class="number">0</span>, <span class="number">0</span>);</div><div class="line">            x2[i] = i &lt; len2 ? ComplexFFT(str2[len2 - i - <span class="number">1</span>] - <span class="string">'0'</span>, <span class="number">0</span>) : ComplexFFT(<span class="number">0</span>, <span class="number">0</span>);</div><div class="line">        &#125;</div><div class="line">        FFT(x1, len, <span class="number">1</span>);</div><div class="line">        FFT(x2, len, <span class="number">1</span>);</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len; i++) &#123;</div><div class="line">            x[i] = x1[i] * x2[i];</div><div class="line">        &#125;</div><div class="line">        FFT(x, len, <span class="number">-1</span>);</div><div class="line">        sum[len] = <span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len; i++) &#123;</div><div class="line">            sum[i] = (<span class="keyword">int</span>)(x[i].a + <span class="number">0.5</span>);</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len; i++) &#123;</div><div class="line">            sum[i+<span class="number">1</span>] += sum[i] / <span class="number">10</span>;</div><div class="line">            sum[i] %= <span class="number">10</span>;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = len; i &gt;= <span class="number">0</span>; i--) &#123;</div><div class="line">            <span class="keyword">if</span> (sum[i] != <span class="number">0</span>) &#123;</div><div class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> j = i; j &gt;= <span class="number">0</span>; j--) &#123;</div><div class="line">                    <span class="built_in">printf</span>(<span class="string">"%d"</span>, sum[j]);</div><div class="line">                &#125;</div><div class="line">                <span class="keyword">break</span>;</div><div class="line">            &#125;</div><div class="line">            <span class="keyword">if</span> (i == <span class="number">0</span>) <span class="built_in">printf</span>(<span class="string">"0"</span>);</div><div class="line">        &#125;</div><div class="line">        <span class="built_in">printf</span>(<span class="string">"\n"</span>);</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h1 id="压8位的高精度乘法"><a href="#压8位的高精度乘法" class="headerlink" title="压8位的高精度乘法"></a>压8位的高精度乘法</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> TEN[] = &#123;<span class="number">1</span>, <span class="number">10</span>, <span class="number">100</span>, <span class="number">1000</span>, <span class="number">10000</span>, <span class="number">100000</span>, </div><div class="line">    <span class="number">1000000</span>, <span class="number">10000000</span>, <span class="number">100000000</span>&#125;;</div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> MV = <span class="number">100000000</span>;</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">BigInt</span> &#123;</span></div><div class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; a;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">Handle</span><span class="params">()</span> </span>&#123;</div><div class="line">        <span class="keyword">int</span> n = (<span class="keyword">int</span>)a.size();</div><div class="line">        <span class="keyword">while</span> (n &amp;&amp; a[n<span class="number">-1</span>] == <span class="number">0</span>) n--;</div><div class="line">        a.resize(n);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    BigInt() &#123;&#125;</div><div class="line"></div><div class="line">    BigInt(LL x) &#123;</div><div class="line">        <span class="keyword">while</span> (x) &#123;</div><div class="line">            a.push_back(x % MV);</div><div class="line">            x /= MV;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    BigInt(<span class="keyword">const</span> <span class="built_in">string</span> &amp;s) &#123;</div><div class="line">        <span class="keyword">int</span> slen = s.length();</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = slen - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i -= <span class="number">8</span>) &#123;</div><div class="line">            <span class="keyword">int</span> x = <span class="number">0</span>;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; <span class="number">8</span>; j++) &#123;</div><div class="line">                <span class="keyword">if</span> (i &gt;= j) x += TEN[j] * (s[i-j] - <span class="string">'0'</span>);</div><div class="line">                <span class="keyword">else</span> <span class="keyword">break</span>;</div><div class="line">            &#125;</div><div class="line">            a.push_back(x);</div><div class="line">        &#125;</div><div class="line">        Handle();</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    BigInt(<span class="keyword">char</span> *s) &#123;</div><div class="line">        <span class="keyword">int</span> slen = <span class="built_in">strlen</span>(s);</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = slen - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i -= <span class="number">8</span>) &#123;</div><div class="line">            <span class="keyword">int</span> x = <span class="number">0</span>;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; <span class="number">8</span>; j++) &#123;</div><div class="line">                <span class="keyword">if</span> (i &gt;= j) x += TEN[j] * (s[i-j] - <span class="string">'0'</span>);</div><div class="line">            &#125;</div><div class="line">            a.push_back(x);</div><div class="line">        &#125;</div><div class="line">        Handle();</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="comment">//x &lt; y返回负数, x == y返回0, x &gt; y返回正数</span></div><div class="line">    <span class="function"><span class="keyword">friend</span> <span class="keyword">int</span> <span class="title">Cmp</span><span class="params">(<span class="keyword">const</span> BigInt &amp;x, <span class="keyword">const</span> BigInt &amp;y)</span> </span>&#123;</div><div class="line">        <span class="keyword">if</span> (x.a.size() == y.a.size()) &#123;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = (<span class="keyword">int</span>)x.a.size() - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i--) &#123;</div><div class="line">                <span class="keyword">if</span> (x.a[i] != y.a[i]) <span class="keyword">return</span> x.a[i] - y.a[i];</div><div class="line">            &#125;</div><div class="line">            <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">        &#125; <span class="keyword">else</span> &#123;</div><div class="line">            <span class="keyword">return</span> (<span class="keyword">int</span>)x.a.size() - (<span class="keyword">int</span>)y.a.size();</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">friend</span> BigInt <span class="keyword">operator</span>+(<span class="keyword">const</span> BigInt &amp;x, <span class="keyword">const</span> BigInt &amp;y) &#123;</div><div class="line">        BigInt r;</div><div class="line">        <span class="keyword">int</span> xs = x.a.size(), ys = y.a.size(), sp = <span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; xs || i &lt; ys; i++) &#123;</div><div class="line">            <span class="keyword">int</span> u;</div><div class="line">            <span class="keyword">if</span> (i &gt;= xs) u = y.a[i] + sp;</div><div class="line">            <span class="keyword">else</span> <span class="keyword">if</span> (i &gt;= ys) u = x.a[i] + sp;</div><div class="line">            <span class="keyword">else</span> u = x.a[i] + y.a[i] + sp;</div><div class="line">            <span class="keyword">if</span> (u &gt;= MV) &#123;</div><div class="line">                r.a.push_back(u - MV);</div><div class="line">                sp = <span class="number">1</span>;</div><div class="line">            &#125; <span class="keyword">else</span> &#123;</div><div class="line">                r.a.push_back(u);</div><div class="line">                sp = <span class="number">0</span>;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">        r.a.push_back(sp);</div><div class="line">        r.Handle();</div><div class="line">        <span class="keyword">return</span> r;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">friend</span> BigInt <span class="keyword">operator</span>-(<span class="keyword">const</span> BigInt &amp;x, <span class="keyword">const</span> BigInt &amp;y) &#123;</div><div class="line">        BigInt r;</div><div class="line">        <span class="keyword">int</span> cmp = Cmp(x, y), u, sp = <span class="number">0</span>;</div><div class="line">        <span class="keyword">int</span> xs = x.a.size(), ys = y.a.size();</div><div class="line">        <span class="keyword">if</span> (cmp == <span class="number">0</span>) &#123;</div><div class="line">            <span class="keyword">return</span> r;</div><div class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (cmp &gt; <span class="number">0</span>) &#123;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; xs; i++) &#123;</div><div class="line">                <span class="keyword">if</span> (i &gt;= ys) u = x.a[i] + sp;</div><div class="line">                <span class="keyword">else</span> u = x.a[i] - y.a[i] + sp;</div><div class="line">                <span class="keyword">if</span> (u &lt; <span class="number">0</span>) &#123;</div><div class="line">                    u += MV;</div><div class="line">                    sp = <span class="number">-1</span>;</div><div class="line">                &#125; <span class="keyword">else</span> &#123;</div><div class="line">                    sp = <span class="number">0</span>;</div><div class="line">                &#125;</div><div class="line">                r.a.push_back(u);</div><div class="line">            &#125;</div><div class="line">        &#125; <span class="keyword">else</span> &#123;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; ys; i++) &#123;</div><div class="line">                <span class="keyword">if</span> (i &gt;= xs) u = y.a[i] + sp;</div><div class="line">                <span class="keyword">else</span> u = y.a[i] - x.a[i] + sp;</div><div class="line">                <span class="keyword">if</span> (u &lt; <span class="number">0</span>) &#123;</div><div class="line">                    u += MV;</div><div class="line">                    sp = <span class="number">-1</span>;</div><div class="line">                &#125; <span class="keyword">else</span> &#123;</div><div class="line">                    sp = <span class="number">0</span>;</div><div class="line">                &#125;</div><div class="line">                r.a.push_back(u);</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">        r.Handle();</div><div class="line">        <span class="keyword">return</span> r;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="comment">//O(n * m)普通乘法</span></div><div class="line">    <span class="keyword">friend</span> BigInt <span class="keyword">operator</span>*(<span class="keyword">const</span> BigInt &amp;x, <span class="keyword">const</span> BigInt &amp;y) &#123;</div><div class="line">        <span class="keyword">int</span> xs = (<span class="keyword">int</span>)x.a.size(), ys = (<span class="keyword">int</span>)y.a.size(), tot = xs + ys;</div><div class="line">        BigInt r;</div><div class="line">        <span class="built_in">vector</span>&lt;LL&gt; v(xs + ys, <span class="number">0L</span>L);</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; xs; i++) &#123;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; ys; j++) &#123;</div><div class="line">                v[i+j] += (LL)x.a[i] * (LL)y.a[j];</div><div class="line">                v[i+j+<span class="number">1</span>] += v[i+j] / MV;</div><div class="line">                v[i+j] %= MV;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; tot; i++)</div><div class="line">            r.a.push_back((<span class="keyword">int</span>)v[i]);</div><div class="line">        r.Handle();</div><div class="line">        <span class="keyword">return</span> r;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">friend</span> BigInt <span class="keyword">operator</span>/(<span class="keyword">const</span> BigInt &amp;x, <span class="keyword">int</span> y) &#123;</div><div class="line">        BigInt r;</div><div class="line">        LL u = <span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = (<span class="keyword">int</span>)x.a.size() - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i--) &#123;</div><div class="line">            u = u * MV + x.a[i];</div><div class="line">            r.a.push_back((<span class="keyword">int</span>)(u / y));</div><div class="line">            u %= y;</div><div class="line">        &#125;</div><div class="line">        reverse(r.a.begin(), r.a.end());</div><div class="line">        r.Handle();</div><div class="line">        <span class="keyword">return</span> r;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">friend</span> <span class="keyword">int</span> <span class="keyword">operator</span>%(<span class="keyword">const</span> BigInt &amp;x, <span class="keyword">int</span> y) &#123;</div><div class="line">        LL u = <span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = (<span class="keyword">int</span>)x.a.size() - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i--) &#123;</div><div class="line">            u = u * MV + x.a[i];</div><div class="line">            u %= y;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">return</span> u;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">friend</span> istream&amp; <span class="keyword">operator</span>&gt;&gt;(istream&amp; in, BigInt &amp;x) &#123;</div><div class="line">        <span class="built_in">string</span> s; <span class="built_in">cin</span> &gt;&gt; s;</div><div class="line">        x = BigInt(s);</div><div class="line">        <span class="keyword">return</span> in;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">friend</span> ostream&amp; <span class="keyword">operator</span>&lt;&lt;(ostream&amp; out, <span class="keyword">const</span> BigInt &amp;x) &#123;</div><div class="line">        <span class="keyword">int</span> n = (<span class="keyword">int</span>)x.a.size() - <span class="number">1</span>;</div><div class="line">        <span class="keyword">if</span> (n &lt; <span class="number">0</span>) &#123;</div><div class="line">            out &lt;&lt; <span class="number">0</span>;</div><div class="line">        &#125; <span class="keyword">else</span> &#123;</div><div class="line">            out &lt;&lt; x.a[n--];</div><div class="line">            <span class="keyword">while</span> (n &gt;= <span class="number">0</span>) out &lt;&lt; setfill(<span class="string">'0'</span>) &lt;&lt; setw(<span class="number">8</span>) &lt;&lt; x.a[n--];</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">return</span> out;</div><div class="line">    &#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="keyword">char</span> a[<span class="number">50010</span>], b[<span class="number">50010</span>];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    BigInt x, y;</div><div class="line">    <span class="keyword">while</span> (<span class="built_in">cin</span> &gt;&gt; x &gt;&gt; y) &#123;</div><div class="line">        <span class="built_in">cout</span> &lt;&lt; x * y &lt;&lt; <span class="built_in">endl</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/poj2109/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/poj2109/" itemprop="url">poj 2109 Power of Cryptography (高精度+二分)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-15T00:00:00+08:00">
                2017-03-15
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/poj2109/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/poj2109/" class="cy_cmt_count" data-xid="poj2109/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>对$[1, 10^9]$进行二分查找即可，不过需要注意的是应该是数据问题吧，需要向下取整才能AC。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight java"><table><tr><td class="code"><pre><div class="line"><span class="keyword">import</span> java.util.*;</div><div class="line"><span class="keyword">import</span> java.math.*;</div><div class="line"></div><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Main</span> </span>&#123;</div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">static</span> BigInteger <span class="title">binarySearch</span><span class="params">(BigInteger l, BigInteger r, <span class="keyword">int</span> n, BigInteger p)</span> </span>&#123;</div><div class="line">        BigInteger ans = <span class="keyword">new</span> BigInteger(<span class="string">"0"</span>);</div><div class="line">        <span class="keyword">while</span> (l.compareTo(r) &lt;= <span class="number">0</span>) &#123;</div><div class="line">            BigInteger mid = l.add(r).shiftRight(<span class="number">1</span>);</div><div class="line">            <span class="keyword">int</span> cp = mid.pow(n).compareTo(p);</div><div class="line">            <span class="keyword">if</span> (cp == <span class="number">0</span>) &#123;</div><div class="line">                <span class="keyword">return</span> mid;</div><div class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (cp &lt; <span class="number">0</span>) &#123;</div><div class="line">                ans = mid;</div><div class="line">                l = mid.add(BigInteger.ONE);</div><div class="line">            &#125; <span class="keyword">else</span> &#123;</div><div class="line">                r = mid.subtract(BigInteger.ONE);</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">return</span> ans;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String [] args)</span> </span>&#123;</div><div class="line">        Scanner sc = <span class="keyword">new</span> Scanner(System.in);</div><div class="line"></div><div class="line">        <span class="keyword">while</span> (sc.hasNext()) &#123;</div><div class="line">            <span class="keyword">int</span> n = sc.nextInt();</div><div class="line">            BigInteger p = sc.nextBigInteger();</div><div class="line"></div><div class="line">            BigInteger k = binarySearch(BigInteger.ONE, BigInteger.valueOf(<span class="number">1000000000</span>), n, p);</div><div class="line">            System.out.println(k);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/uva10934/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/uva10934/" itemprop="url">uva 10934 Dropping water balloons (动态规划)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-13T00:00:00+08:00">
                2017-03-13
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/uva10934/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/uva10934/" class="cy_cmt_count" data-xid="uva10934/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>设$dp<em>{i,j}$表示$i$个球抛$j$次可以确定的最大高度。<br>那么我们第一次在$dp</em>{i-1,j-1}+1$层处抛置小球。<br>这样的话，如果这一层碎了，我们可以通过$i-1$个球抛$j-1$次来判断球会在下面哪一层碎掉。<br>若是第一次没碎，那么我们可以再通过$i$个球抛$j-1$次来向上判断$dp<em>{i,j-1}$层。<br>最终dp方程为：$dp</em>{i,j} = dp<em>{i-1,j-1} + 1 + dp</em>{i,j-1}$。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</div><div class="line"></div><div class="line">LL dp[<span class="number">105</span>][<span class="number">64</span>];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="built_in">memset</span>(dp, <span class="number">0</span>, <span class="keyword">sizeof</span>(dp));</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= <span class="number">100</span>; i++) &#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt;= <span class="number">63</span>; j++)</div><div class="line">            dp[i][j] = dp[i<span class="number">-1</span>][j<span class="number">-1</span>] + <span class="number">1</span> + dp[i][j<span class="number">-1</span>];</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">int</span> k; LL n;</div><div class="line">    <span class="keyword">while</span> (<span class="built_in">scanf</span>(<span class="string">"%d%lld"</span>, &amp;k, &amp;n) != EOF &amp;&amp; k != <span class="number">0</span>) &#123;</div><div class="line">        <span class="keyword">bool</span> flag = <span class="literal">true</span>;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= <span class="number">63</span>; i++) &#123;</div><div class="line">            <span class="keyword">if</span> (dp[k][i] &gt;= n) &#123;</div><div class="line">                <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, i);</div><div class="line">                flag = <span class="literal">false</span>;</div><div class="line">                <span class="keyword">break</span>;</div><div class="line">            &#125;</div><div class="line">        &#125; </div><div class="line">        <span class="keyword">if</span> (flag) <span class="built_in">printf</span>(<span class="string">"More than 63 trials needed.\n"</span>);</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/ural1682/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/ural1682/" itemprop="url">ural 1682 Crazy Professor (并查集)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-12T00:00:00+08:00">
                2017-03-12
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/ural1682/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/ural1682/" class="cy_cmt_count" data-xid="ural1682/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>我们不难发现$1, k - 1, 2k - 1$满足条件，所以最终答案一定小于$2k$。<br>那么我们只需要从$1$开始枚举，不妨设当前枚举到$i$，每次将所有的$j(j &lt; i \&amp;\&amp; ((j^2 + i) \% k == 0 || (i^2 + j) \% k == 0))$与$i$进行合并，直到$i$和$j$本来就属于同一集合为止。<br>需要注意的一种情况i和j同时满足$(j^2 + i) % k == 0，(i^2 + j) % k == 0$这两个条件。(这个地方WA哭了)</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> K = <span class="number">100010</span>;</div><div class="line"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; a[K * <span class="number">2</span>], b[K * <span class="number">2</span>];</div><div class="line"><span class="keyword">int</span> fat[K * <span class="number">2</span>], vis[K * <span class="number">2</span>];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">int</span> <span class="title">GetFat</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</div><div class="line">    <span class="keyword">return</span> x == fat[x] ? x : fat[x] = GetFat(fat[x]);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">Union</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y)</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> fx = GetFat(x), fy = GetFat(y);</div><div class="line">    <span class="keyword">if</span> (fx != fy) fat[fy] = fx;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">bool</span> <span class="title">InSame</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y)</span> </span>&#123;</div><div class="line">    <span class="keyword">return</span> GetFat(x) == GetFat(y);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="built_in">memset</span>(vis, <span class="number">0</span>, <span class="keyword">sizeof</span>(vis));</div><div class="line">    <span class="keyword">int</span> k; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;k);</div><div class="line">    <span class="keyword">if</span> (k == <span class="number">1</span>) &#123;</div><div class="line">        <span class="built_in">printf</span>(<span class="string">"3\n"</span>);</div><div class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (k == <span class="number">2</span>) &#123;</div><div class="line">        <span class="built_in">printf</span>(<span class="string">"5\n"</span>);</div><div class="line">    &#125; <span class="keyword">else</span> &#123;</div><div class="line">        <span class="keyword">int</span> n = k &lt;&lt; <span class="number">1</span>;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; n; i++) &#123;</div><div class="line">            a[i % k].push_back(i);</div><div class="line">            b[(LL)i * i % k].push_back(i);</div><div class="line">            fat[i] = i;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; n; i++) &#123;</div><div class="line">            <span class="keyword">int</span> t1 = (<span class="keyword">int</span>)((k - (LL)i * i % k) % k);</div><div class="line">            <span class="keyword">int</span> t2 = (<span class="keyword">int</span>)((k - i % k) % k);</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; a[t1].size() &amp;&amp; a[t1][j] &lt; i; j++) &#123;</div><div class="line">                <span class="keyword">if</span> (InSame(i, a[t1][j])) &#123;</div><div class="line">                    <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, i);</div><div class="line">                    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">                &#125; <span class="keyword">else</span> &#123;</div><div class="line">                    Union(i, a[t1][j]);</div><div class="line">                    vis[a[t1][j]] = i;</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; b[t2].size() &amp;&amp; b[t2][j] &lt; i; j++) &#123;</div><div class="line">                <span class="keyword">if</span> (vis[b[t2][j]] == i) <span class="keyword">continue</span>;</div><div class="line">                <span class="keyword">if</span> (InSame(i, b[t2][j])) &#123;</div><div class="line">                    <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, i);</div><div class="line">                    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">                &#125; <span class="keyword">else</span> &#123;</div><div class="line">                    Union(i, b[t2][j]);</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/poj3622/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/poj3622/" itemprop="url">poj 3622 Gourmet Grazers (贪心)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-11T00:00:00+08:00">
                2017-03-11
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/poj3622/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/poj3622/" class="cy_cmt_count" data-xid="poj3622/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>设一个空集合s用来存放草的价格。<br>先将牛和草分别按score从大到小排序，然后枚举奶牛，之后将所有的score比当前牛score的草的price加入到集合s中，因为已经牛的score已经从大到小排序过了，所以集合中的所有的草的score一定会比后面的牛的score大，这样就可以排除掉score的影响。<br>接下来我们只需要考虑price即可，不难发现我们每次只需要从集合中找出大于等于当前牛的price的最小草的price。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstring&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;set&gt;</span></span></div><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;map&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</div><div class="line"><span class="keyword">typedef</span> <span class="built_in">set</span>&lt;<span class="keyword">int</span>&gt;::iterator SIT;</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Data</span> &#123;</span></div><div class="line">    <span class="keyword">int</span> price, score;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">bool</span> <span class="title">Cmp</span><span class="params">(<span class="keyword">const</span> Data &amp;a, <span class="keyword">const</span> Data &amp;b)</span> </span>&#123;</div><div class="line">    <span class="keyword">return</span> a.score == b.score ? a.price &lt; b.price : a.score &gt; b.score;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">100010</span>;</div><div class="line"><span class="keyword">int</span> n, m;</div><div class="line">Data a[N], b[N];</div><div class="line"><span class="built_in">set</span>&lt;<span class="keyword">int</span>&gt; s;</div><div class="line"><span class="built_in">map</span>&lt;<span class="keyword">int</span>, <span class="keyword">int</span>&gt; mm;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;n, &amp;m);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;a[i].price, &amp;a[i].score);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= m; i++) <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;b[i].price, &amp;b[i].score);</div><div class="line">    sort(a + <span class="number">1</span>, a + n + <span class="number">1</span>, Cmp);</div><div class="line">    sort(b + <span class="number">1</span>, b + m + <span class="number">1</span>, Cmp);</div><div class="line">    LL ans = <span class="number">0</span>, cnt = <span class="number">1</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        <span class="keyword">while</span> (cnt &lt;= m &amp;&amp; b[cnt].score &gt;= a[i].score) &#123;</div><div class="line">            s.insert(b[cnt].price);</div><div class="line">            mm[b[cnt].price]++;</div><div class="line">            cnt++;</div><div class="line">        &#125;</div><div class="line">        SIT sit = s.lower_bound(a[i].price);</div><div class="line">        <span class="keyword">if</span> (sit == s.end()) &#123;</div><div class="line">            <span class="built_in">printf</span>(<span class="string">"-1\n"</span>);</div><div class="line">            <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">        &#125; <span class="keyword">else</span> &#123;</div><div class="line">            ans += *sit;</div><div class="line">            mm[*sit]--;</div><div class="line">            <span class="keyword">if</span> (mm[*sit] == <span class="number">0</span>) s.erase(sit);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="built_in">printf</span>(<span class="string">"%lld\n"</span>, ans);</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <a class="extend prev" rel="prev" href="/page/7/"><i class="fa fa-angle-left"></i></a><a class="page-number" href="/">1</a><span class="space">&hellip;</span><a class="page-number" href="/page/7/">7</a><span class="page-number current">8</span><a class="page-number" href="/page/9/">9</a><span class="space">&hellip;</span><a class="page-number" href="/page/11/">11</a><a class="extend next" rel="next" href="/page/9/"><i class="fa fa-angle-right"></i></a>
  </nav>



          </div>
          


          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="/img/head.png"
                alt="cayun" />
            
              <p class="site-author-name" itemprop="name">cayun</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">102</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">3</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">79</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          <div class="links-of-author motion-element">
            
              
                <span class="links-of-author-item">
                  <a href="https://github.com/comeacrossyun" target="_blank" title="GitHub">
                    
                      <i class="fa fa-fw fa-github"></i>GitHub</a>
                </span>
              
                <span class="links-of-author-item">
                  <a href="mailto:comeacrossyun@gmail.com" target="_blank" title="E-Mail">
                    
                      <i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                </span>
              
            
          </div>

          
          

          
          

          

        </div>
      </section>

      

      
        <div class="back-to-top">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2017</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">cayun</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Pisces</a></div>




        







        
      </div>
    </footer>

    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.3"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.3"></script>



  

  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.3"></script>



  


  




	





  





  




  
    <script id="cy_cmt_num" src="https://changyan.sohu.com/upload/plugins/plugins.list.count.js?clientId=cyt6VLWhj"></script>
  









  





  

  
<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script>


  
  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.bootcss.com/mathjax/2.7.1/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  

  

</body>
</html>
